{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Refueling Stops"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #dynamic-programming #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #动态规划 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minRefuelStops"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最低加油次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>汽车从起点出发驶向目的地，该目的地位于出发位置东面 <code>target</code>&nbsp;英里处。</p>\n",
    "\n",
    "<p>沿途有加油站，用数组&nbsp;<code>stations</code> 表示。其中 <code>stations[i] = [position<sub>i</sub>, fuel<sub>i</sub>]</code> 表示第 <code>i</code> 个加油站位于出发位置东面&nbsp;<code>position<sub>i</sub></code> 英里处，并且有&nbsp;<code>fuel<sub>i</sub></code>&nbsp;升汽油。</p>\n",
    "\n",
    "<p>假设汽车油箱的容量是无限的，其中最初有&nbsp;<code>startFuel</code>&nbsp;升燃料。它每行驶 1 英里就会用掉 1 升汽油。当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。</p>\n",
    "\n",
    "<p>为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>注意：如果汽车到达加油站时剩余燃料为 <code>0</code>，它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 <code>0</code>，仍然认为它已经到达目的地。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>target = 1, startFuel = 1, stations = []\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>可以在不加油的情况下到达目的地。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>target = 100, startFuel = 1, stations = [[10,100]]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>无法抵达目的地，甚至无法到达第一个加油站。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "出发时有 10 升燃料。\n",
    "开车来到距起点 10 英里处的加油站，消耗 10 升燃料。将汽油从 0 升加到 60 升。\n",
    "然后，从 10 英里处的加油站开到 60 英里处的加油站（消耗 50 升燃料），\n",
    "并将汽油从 10 升加到 50 升。然后开车抵达目的地。\n",
    "沿途在两个加油站停靠，所以返回 2 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= target, startFuel &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>0 &lt;= stations.length &lt;= 500</code></li>\n",
    "\t<li><code>1 &lt;= position<sub>i</sub> &lt; position<sub>i+1</sub> &lt; target</code></li>\n",
    "\t<li><code>1 &lt;= fuel<sub>i</sub> &lt; 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-refueling-stops](https://leetcode.cn/problems/minimum-number-of-refueling-stops/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-refueling-stops](https://leetcode.cn/problems/minimum-number-of-refueling-stops/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1\\n1\\n[]', '100\\n1\\n[[10,100]]', '100\\n10\\n[[10,60],[20,30],[30,30],[60,40]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        n = len(stations)\n",
    "        ans, fuel, prev, h = 0, startFuel, 0, []\n",
    "        for i in range(n + 1):\n",
    "            curr = stations[i][0] if i < n else target\n",
    "            fuel -= curr - prev\n",
    "            while fuel < 0 and h:\n",
    "                fuel -= heappop(h)\n",
    "                ans += 1\n",
    "            if fuel < 0:\n",
    "                return -1\n",
    "            if i < n:\n",
    "                heappush(h, -stations[i][1])\n",
    "                prev = curr\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, t: int, s: int, stations: List[List[int]]) -> int:\n",
    "        stations.sort()\n",
    "        a=0\n",
    "        stuck=[]\n",
    "        st=1\n",
    "        ans=0\n",
    "        b=0\n",
    "        for b in range(a,len(stations)):\n",
    "            if s>=stations[b][0]:\n",
    "                heapq.heappush(stuck,-stations[b][1])\n",
    "            else:\n",
    "                while stuck and s<stations[b][0]:\n",
    "                    s-=heapq.heappop(stuck)\n",
    "                    ans+=1\n",
    "                if s<stations[b][0]:\n",
    "                    break\n",
    "                else:\n",
    "                    heapq.heappush(stuck,-stations[b][1])\n",
    "        while stuck and s<t:\n",
    "            s-=heapq.heappop(stuck)\n",
    "            ans+=1\n",
    "        if s>=t:\n",
    "            return (ans)\n",
    "        else:\n",
    "            return (-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "\n",
    "        ans = 0\n",
    "        total = startFuel\n",
    "        stations = stations[::-1]\n",
    "        h = [0]\n",
    "        while h:\n",
    "            if total >= target:\n",
    "                return ans\n",
    "            while stations and total >= stations[-1][0]:\n",
    "                pos, vol = stations.pop()\n",
    "                heappush(h, -vol)\n",
    "            total -= heappop(h)\n",
    "            ans += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "\n",
    "        ans = 0\n",
    "        total = startFuel\n",
    "        stations.sort(reverse=True)\n",
    "        h = [0]\n",
    "        while h:\n",
    "            if total >= target:\n",
    "                return ans\n",
    "            while stations and total >= stations[-1][0]:\n",
    "                pos, vol = stations.pop()\n",
    "                heappush(h, -vol)\n",
    "            total -= heappop(h)\n",
    "            ans += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\r\n",
    "class Solution:\r\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\r\n",
    "        stations.append([target,0])\r\n",
    "        n=len(stations)\r\n",
    "        fuels=[]\r\n",
    "        cur_fuel=startFuel\r\n",
    "        cur_pos=0\r\n",
    "        idx=0\r\n",
    "        ret=0\r\n",
    "\r\n",
    "        while cur_fuel>=0 or fuels:\r\n",
    "            if idx==n:\r\n",
    "                return ret\r\n",
    "            pos,fuel=stations[idx]\r\n",
    "            dis=pos-cur_pos\r\n",
    "            cur_fuel-=dis\r\n",
    "            cur_pos=pos\r\n",
    "\r\n",
    "            while cur_fuel<0 and fuels:\r\n",
    "                cur_fuel+=-heapq.heappop(fuels)\r\n",
    "                ret+=1\r\n",
    "\r\n",
    "            if cur_fuel<0:\r\n",
    "                return -1\r\n",
    "            \r\n",
    "            heapq.heappush(fuels,-fuel)\r\n",
    "\r\n",
    "            idx+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        stations.append([target,0])\n",
    "        n=len(stations)\n",
    "        for i in range(n):\n",
    "            if startFuel+sum([c[1] for c in stations[:i]])<stations[i][0]:\n",
    "                return -1\n",
    "        q=[]\n",
    "        res=0\n",
    "        hp=startFuel\n",
    "        for i,(p,fu) in enumerate(stations):\n",
    "            hp-=(p-stations[i-1][0] if i>0 else p) \n",
    "            # 如果过不了站,需要前面站的油\n",
    "            while hp<0:\n",
    "                hp+=(-heappop(q))\n",
    "                res+=1\n",
    "            heappush(q, -fu)  # 油备用到下一站\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        n = len(stations)\n",
    "        dp = {}\n",
    "        dp[0] = (0, startFuel)\n",
    "\n",
    "        for i, (pos, fuel) in enumerate(stations):\n",
    "            newdp = {}\n",
    "            for t, (pre_pos, rest_fuel) in dp.items():\n",
    "                if rest_fuel >= pos - pre_pos: \n",
    "                    if t not in newdp:\n",
    "                        newdp[t] = (pos, rest_fuel - pos + pre_pos)\n",
    "                    else:\n",
    "                        if newdp[t][1] < rest_fuel - pos + pre_pos:\n",
    "                            newdp[t] = (pos, rest_fuel - pos + pre_pos)\n",
    "                    if t+1 not in newdp:\n",
    "                        newdp[t+1] = (pos, rest_fuel - pos + pre_pos + fuel)\n",
    "                    else:\n",
    "                        if newdp[t+1][1] < rest_fuel - pos + pre_pos + fuel:\n",
    "                            newdp[t+1] = (pos, rest_fuel - pos + pre_pos + fuel)\n",
    "            \n",
    "            dp = newdp\n",
    "\n",
    "        \n",
    "        print(dp)\n",
    "        ans = inf\n",
    "        for t, (pre_pos, rest_fuel) in dp.items():\n",
    "            if target - pre_pos <= rest_fuel:\n",
    "                ans = min(ans, t)\n",
    "        \n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Heap:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.heap = []\n",
    "\n",
    "    def _up(self, index):\n",
    "\n",
    "        while (parent:= (index+1)//2-1 )>=0:\n",
    "            if self.heap[parent][0]> self.heap[index][0]:\n",
    "                self.heap[index],self.heap[parent] = self.heap[parent],self.heap[index]\n",
    "                index =parent\n",
    "            else:\n",
    "                return \n",
    "\n",
    "    def get_small_child(self,left):\n",
    "        heap_len = len(self.heap)\n",
    "        right =  left+1\n",
    "        if right>=heap_len:\n",
    "            return left\n",
    "        return left if self.heap[left][0]< self.heap[right][0] else right\n",
    "\n",
    "    def _down(self, index):\n",
    "        heap_len = len(self.heap)\n",
    "        while (left := index*2+1)<heap_len:\n",
    "            small_child = self.get_small_child(left)\n",
    "            if self.heap[small_child][0]<self.heap[index][0]:\n",
    "                self.heap[small_child],self.heap[index] = self.heap[index],self.heap[small_child]\n",
    "                index = small_child\n",
    "            else:\n",
    "                return \n",
    "\n",
    "    def pop(self):\n",
    "        if not self.heap:\n",
    "            return None\n",
    "        \n",
    "        self.heap[0],self.heap[-1] = self.heap[-1],self.heap[0]\n",
    "        res = self.heap.pop()\n",
    "        self._down(0)\n",
    "        return res\n",
    "        \n",
    "    def push(self, value):\n",
    "        self.heap.append(value)\n",
    "        self._up(len(self.heap)-1)\n",
    "\n",
    "    \n",
    "    def __bool__(self):\n",
    "        return len(self.heap) != 0\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        distance = 0\n",
    "        oil = startFuel\n",
    "        heap = Heap()\n",
    "        for i, (x,y) in enumerate(stations):\n",
    "            if (the_oil:=distance+oil-x) >=0:\n",
    "                heap.push([y, x,the_oil,i])\n",
    "                distance =x\n",
    "                oil =the_oil+y\n",
    "            else:\n",
    "                return -1\n",
    "        if (sur_dis:=distance+oil-target)<0:\n",
    "            return -1\n",
    "        max_station_index = len(stations)-1\n",
    "        need_station = len(stations)\n",
    "        # print(\"sur_dis\",sur_dis)\n",
    "        # print(heap.heap)\n",
    "        stations_len = len(stations)\n",
    "        t_sorted = sorted(heap.heap,key=lambda x : x[-1])\n",
    "        while (t:=heap.pop()) is not None:\n",
    "            station_oil, cur_dis, sur_oil, index = t\n",
    "            # print(station_oil, cur_dis, sur_oil, index)\n",
    "            if sur_oil<0:\n",
    "                # print(\"continue\")\n",
    "                continue\n",
    "            if station_oil>sur_dis:\n",
    "                return need_station\n",
    "            fat_most_dis = cur_dis+sur_oil\n",
    "            if max_station_index == index:\n",
    "                if fat_most_dis>= target:\n",
    "                    need_station-=1\n",
    "                    sur_dis -= station_oil\n",
    "            else:\n",
    "                next_dist,next_oil  = stations[index+1]\n",
    "                if fat_most_dis >=next_dist:\n",
    "                    if all( t_sorted[i][-2]-station_oil >=0 for i in range(index+1, stations_len)):\n",
    "                        need_station-=1\n",
    "                        # sur_dis -= station_oil\n",
    "                        for i in range(index+1, stations_len):\n",
    "                            data = t_sorted[i]\n",
    "                            data[-2] -=station_oil\n",
    "                        sur_dis -= station_oil\n",
    "        return need_station\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        # 对于途中的每个站点，都可以选择加油或者不加油，加油会增加次数，但是能增加存油量。\n",
    "        # 显然，我们的目标是次数更少，存油量更多，这样才能以更少的次数，走的更远。\n",
    "        # 所以本题实际上是最短路径问题。\n",
    "        # 加油站最多有500个，并且一定是按升序排列的。\n",
    "        # 从起点开始，我可以选择不加油，也可以选择在每个站都加油。\n",
    "        # 在次数相同时，选择的加油站不同，对应的路线也不同。\n",
    "        N = len(stations)\n",
    "        # 2、动态规划\n",
    "        # 到各站不同的加油次数所能到大的最远距离。\n",
    "        # dp = [[-1]*(N+1) for _ in range(2)]\n",
    "        # dp[1][0] = startFuel\n",
    "        # for i in range(N):\n",
    "        #     dp[0],dp[1] = dp[1],dp[0]\n",
    "        #     d,f = stations[i]\n",
    "        #     # 第X站最多可加X次油\n",
    "        #     for j in range(i+2):\n",
    "        #         dp[1][j] = -1\n",
    "        #         # 上一站的j次加油能否到达本站\n",
    "        #         if dp[0][j] >= d: dp[1][j] = dp[0][j]\n",
    "        #         # 上一站的j-1次加油能否到达本站\n",
    "        #         if j>0 and dp[0][j-1] >= d: dp[1][j] = max(dp[1][j],dp[0][j-1]+f) \n",
    "        #     # print(i,dp[1])\n",
    "        # for i in range(N+1):\n",
    "        #     if dp[1][i] >= target: return i\n",
    "        # return -1\n",
    "        # 1、优先队列\n",
    "        # 三元组：次数，总行驶里程，最近的可加油站点。\n",
    "        pq = [(0,-startFuel,0)]\n",
    "        visited = [[False]*(N+1) for _ in range(N)]\n",
    "        while pq:\n",
    "            cnt,fuel,start = heapq.heappop(pq)\n",
    "            if target+fuel <= 0: return cnt\n",
    "            for i in range(start,N):\n",
    "                d,f = stations[i]\n",
    "                # 站点不可达\n",
    "                if d+fuel > 0: break\n",
    "                if visited[i][cnt+1]: continue\n",
    "                visited[i][cnt+1] = True\n",
    "                heapq.heappush(pq,(cnt+1,fuel-f,i+1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(stations)\n",
    "\n",
    "        if n == 0:\n",
    "            if startFuel >= target:\n",
    "                return 0\n",
    "            \n",
    "            return -1\n",
    "\n",
    "        for i in range(n-1,0,-1):\n",
    "            stations[i][0] -= stations[i-1][0]\n",
    "\n",
    "        if startFuel >= target:\n",
    "            return 0\n",
    "\n",
    "        dp = []\n",
    "\n",
    "        minCharge = float('inf')\n",
    "        remainingDistance = target\n",
    "        for i, station in enumerate(stations):\n",
    "            remainingDistance -= station[0]\n",
    "            dp.append({})\n",
    "            if len(dp) == 1:\n",
    "                fuel = startFuel - station[0]\n",
    "                if fuel < 0:\n",
    "                    break\n",
    "\n",
    "                dp[i][0] = fuel\n",
    "                fuel += station[1]\n",
    "                if fuel >= remainingDistance:\n",
    "                    minCharge = 1\n",
    "                    break\n",
    "                \n",
    "                dp[i][1] = fuel\n",
    "            else:\n",
    "\n",
    "                for k,v in dp[i-1].items():\n",
    "                    fuel = v - station[0]\n",
    "                    if fuel < 0:\n",
    "                        continue\n",
    "                    else:\n",
    "                        if k not in dp[i]:\n",
    "                            dp[i][k] = fuel\n",
    "                        else:\n",
    "                            dp[i][k] = max(dp[i][k], fuel)\n",
    "                        \n",
    "                        fuel += station[1]\n",
    "                        #print(f'{fuel}_{remainingDistance}')\n",
    "                        if fuel >= remainingDistance:\n",
    "                            if minCharge > k+1:\n",
    "                                minCharge = k+1\n",
    "                            continue\n",
    "                        else:\n",
    "                            if (k+1) not in dp[i]:\n",
    "                                dp[i][k+1] = fuel\n",
    "                            else:\n",
    "                                dp[i][k+1] = max(dp[i][k+1], fuel)\n",
    "        \n",
    "        #print(dp)\n",
    "\n",
    "        if minCharge < float('inf'):\n",
    "            return minCharge\n",
    "        \n",
    "        return -1\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        if startFuel >= target:\n",
    "            return 0\n",
    "\n",
    "        n = len(stations)\n",
    "        # dp[i][j] add j times until i station\n",
    "        dp = [[0 for j in range(n+1)] for i in range(n+1)]\n",
    "        # if we never add fuel\n",
    "        # dp[0][0] = startFuel\n",
    "        # for i in range(n):\n",
    "        #     if stations[i][0] <= startFuel:\n",
    "        #         dp[i+1][0] = startFuel\n",
    "\n",
    "        for i in range(n+1):\n",
    "            dp[i][0] = startFuel\n",
    "\n",
    "\n",
    "        for j in range(1, n+1):\n",
    "            for i in range(j, n+1):\n",
    "                dp[i][j] = dp[i-1][j]\n",
    "                if dp[i][j-1] >= stations[i-1][0]:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i-1][j-1] + stations[i-1][1])\n",
    "                if dp[i][j] >= target:\n",
    "                    return j\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        j = startFuel\n",
    "        for i in range(len(stations)):\n",
    "            if j < stations[i][0]:\n",
    "                return -1\n",
    "            j+= stations[i][1]\n",
    "        if j<target:\n",
    "            return -1\n",
    "\n",
    "\n",
    "        if target<= startFuel:\n",
    "            return 0\n",
    "        n = len(stations)+1\n",
    "        dp = [[startFuel]*n for i in range(n)]\n",
    "        count = n\n",
    "        for i in range(1,n):\n",
    "            for j in range(1,i+1):\n",
    "                if (j>=count):\n",
    "                        break\n",
    "                if dp[i-1][j-1]>=stations[i-1][0]:\n",
    "                    dp[i][j] = max(dp[i-1][j-1] + stations[i-1][1],dp[i-1][j])\n",
    "                elif dp[i-1][j]>=stations[i-1][0]:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "\n",
    "               \n",
    "                if dp[i][j] >= target:\n",
    "                        count = min(count,j)\n",
    "        if count == n:\n",
    "            return -1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        if startFuel>=target:return 0\n",
    "        n_station=len(stations)\n",
    "        dp=[[0 for _ in range(n_station+1)] for _ in range(n_station+1)]\n",
    "        \n",
    "        for j in range(n_station+1):\n",
    "            dp[0][j]=startFuel\n",
    "        for i in range(1,n_station+1):\n",
    "            for j in range(i,n_station+1):\n",
    "                if dp[i][j-1]>=stations[j-1][0]:\n",
    "                    dp[i][j]=dp[i][j-1]\n",
    "                if dp[i-1][j-1]>=stations[j-1][0]:\n",
    "                    dp[i][j]=max(dp[i][j],dp[i-1][j-1]+stations[j-1][1])\n",
    "                    # print(j,dp)\n",
    "                if dp[i][j]>=target:\n",
    "                    # print(dp)\n",
    "                    return i\n",
    "        # print(dp)\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "#         for(int i=0;i<n+1;++i)\n",
    "#             dp[i][0]=startFuel; //甭管经过了几个站，一次油也不加那最多跑的就是startFuel的距离\n",
    "        \n",
    "#         for(int i=1;i<n+1;++i)\n",
    "#         {\n",
    "#             for(int j=1;j<=i;++j)\n",
    "#             {\n",
    "#                 if(dp[i-1][j]>=stations[i-1][0])  //在第i站不加油\n",
    "#                     dp[i][j]=dp[i-1][j];\n",
    "#                 if(dp[i-1][j-1]>=stations[i-1][0]) //在第i站加油\n",
    "#                     dp[i][j]=max(dp[i][j],dp[i-1][j-1]+stations[i-1][1]); //加油与否两种情况取大者\n",
    "#             }\n",
    "#         }\n",
    "\n",
    "#         for(int j=0;j<=n;++j)\n",
    "#             if(dp[n][j]>=target)\n",
    "#                 return j;\n",
    "#         return -1;\n",
    "\n",
    "# 作者：tten\n",
    "# 链接：https://leetcode-cn.com/problems/minimum-number-of-refueling-stops/solution/bang-ni-kan-dong-guan-jie-de-dong-tai-gu-8oyf/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        # 对于途中的每个站点，都可以选择加油或者不加油，加油会增加次数，但是能增加存油量。\n",
    "        # 显然，我们的目标是次数更少，存油量更多，这样才能以更少的次数，走的更远。\n",
    "        # 所以本题实际上是最短路径问题。\n",
    "        # 加油站最多有500个，并且一定是按升序排列的。\n",
    "        # 从起点开始，我可以选择不加油，也可以选择在每个站都加油。\n",
    "        # 在次数相同时，选择的加油站不同，对应的路线也不同。\n",
    "        N = len(stations)\n",
    "        # 2、动态规划+贪心\n",
    "        if target <= startFuel: return 0\n",
    "        # 到各站不同的加油次数所能到大的最远距离。\n",
    "        dp = [[-1]*(N+1) for _ in range(N+1)]\n",
    "        dp[0][0] = startFuel\n",
    "        # 对于加油0次的情况\n",
    "        for i in range(1,N+1):\n",
    "            if stations[i-1][0] > startFuel: break\n",
    "            dp[0][i] = startFuel\n",
    "        # 对于加油超过1次的情况\n",
    "        for i in range(1,N+1):\n",
    "            for j in range(N):\n",
    "                # i次和i-1次的上一站加油能否到达本站\n",
    "                if dp[i][j] >= stations[j][0]: dp[i][j+1] = dp[i][j]\n",
    "                if dp[i-1][j] >= stations[j][0]: dp[i][j+1] = max(dp[i][j+1],dp[i-1][j]+stations[j][1])\n",
    "            if dp[i][-1] >= target: return i\n",
    "        return -1\n",
    "        # 1、优先队列\n",
    "        # 三元组：次数，总行驶里程，最近的可加油站点。\n",
    "        # pq = [(0,-startFuel,0)]\n",
    "        # visited = [[False]*(N+1) for _ in range(N)]\n",
    "        # while pq:\n",
    "        #     cnt,fuel,start = heapq.heappop(pq)\n",
    "        #     if target+fuel <= 0: return cnt\n",
    "        #     for i in range(start,N):\n",
    "        #         d,f = stations[i]\n",
    "        #         # 站点不可达\n",
    "        #         if d+fuel > 0: break\n",
    "        #         if visited[i][cnt+1]: continue\n",
    "        #         visited[i][cnt+1] = True\n",
    "        #         heapq.heappush(pq,(cnt+1,fuel-f,i+1))\n",
    "        # return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        # 假设一开始起点和初始燃油就是第0个加油站\n",
    "        stations.insert(0,[0, startFuel])\n",
    "        # 假设目的地是最后一个加油站\n",
    "        stations.append([target,0])\n",
    "        \n",
    "        n = len(stations)\n",
    "        # 到达第i个加油站时的(加油次数: 剩余油量)\n",
    "        dp = [defaultdict(int) for _ in range(n)]\n",
    "        dp[0][0] = startFuel\n",
    "        \n",
    "        res = n\n",
    "        for i in range(1,n):\n",
    "            pos,fuel = stations[i]\n",
    "            lpos = stations[i-1][0]                  \n",
    "            for cnt,lfuel in dp[i-1].items():\n",
    "                # 若到当前加油站还有剩余油量，否则就到不了当前加油站\n",
    "                if lfuel >= pos - lpos:\n",
    "                    tmp = lfuel - (pos-lpos)\n",
    "                    # 剪枝，如果剩余燃油足够到终点，那就不用再选择加不加油了\n",
    "                    if tmp >= target - pos:\n",
    "                        res = min(res,cnt)                        \n",
    "                        continue\n",
    "                                                                \n",
    "                    # 选择不加油\n",
    "                    dp[i][cnt] = max(dp[i][cnt],tmp)                                       \n",
    "                    # 选择加油\n",
    "                    dp[i][cnt+1] = max(dp[i][cnt+1],tmp+fuel) \n",
    "                    #dp[i].add((cnt+1,tmp+fuel))\n",
    "            # 没有一种情况是能到达当前加油站的，返回-1\n",
    "            if not dp[i]:\n",
    "                if res != n:\n",
    "                    return res\n",
    "                else:\n",
    "                    return -1\n",
    "                        \n",
    "        return res        \n",
    "                       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        # 给定 x 次加油机会，最远能到达哪里？\n",
    "        if startFuel >= target:\n",
    "            return 0\n",
    "        n = len(stations)\n",
    "        dp = [[startFuel]*(n+1) for _ in range(n+1)]\n",
    "        for x in range(1, n+1):\n",
    "            for y in range(1, n+1):\n",
    "                dp[x][y] = dp[x][y-1]\n",
    "                if dp[x-1][y-1] >= stations[y-1][0]:\n",
    "                    dp[x][y] = max(dp[x][y], dp[x-1][y-1] + stations[y-1][1])\n",
    "            if dp[x][-1] >= target:\n",
    "                return x\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        # 给定 x 次加油机会，最远能到达哪里？\n",
    "        if startFuel >= target:\n",
    "            return 0\n",
    "        n = len(stations)\n",
    "        dp = [[startFuel]*(n+1) for _ in range(n+1)]\n",
    "        for x in range(1, n+1):\n",
    "            for y in range(1, n+1):\n",
    "                dp[x][y] = dp[x][y-1]\n",
    "                if dp[x-1][y-1] >= stations[y-1][0]:\n",
    "                    dp[x][y] = max(dp[x][y], dp[x-1][y-1] + stations[y-1][1])\n",
    "            if dp[x][-1] >= target:\n",
    "                return x\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        if target<=startFuel:\n",
    "            return 0\n",
    "        n=len(stations)\n",
    "        if n==0:\n",
    "            return -1\n",
    "\n",
    "        # dp[i][j]代表经过前j个站，加了i次油后能到的最远距离\n",
    "        dp=[[-100 for i in range(n+1)] for j in range(n+1)]  \n",
    "        dp[0][0]=startFuel\n",
    "        for j in range(1, n+1):\n",
    "            if stations[j-1][0]<=startFuel:\n",
    "                dp[0][j]=startFuel\n",
    "        # print(dp[0])\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            # j=i的情况\n",
    "            if dp[i-1][i-1]<stations[i-1][0]:\n",
    "                return -1\n",
    "            else:\n",
    "                dp[i][i]=dp[i-1][i-1]+stations[i-1][1]\n",
    "                if dp[i][i]>=target:\n",
    "                    return i\n",
    "            for j in range(i+1, n+1):\n",
    "                # 到达不了的情况\n",
    "                if dp[i][j-1]<stations[j-1][0]:\n",
    "                    break\n",
    "                else:\n",
    "                    dp[i][j]=dp[i][j-1]\n",
    "                    if dp[i-1][j-1]>=stations[j-1][0]:\n",
    "                        dp[i][j]=max(dp[i][j], dp[i-1][j-1]+stations[j-1][1])\n",
    "                    if dp[i][j]>=target:\n",
    "                        return i\n",
    "            # print(dp[i])\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        if startFuel>=target:\n",
    "            return 0\n",
    "        stations=[[0,startFuel]]+stations\n",
    "        n=len(stations)\n",
    "        dp=[[0]*(n) for i in range(n)]\n",
    "        dp[0][0]=stations[0][1]\n",
    "        for i in range(1,n):\n",
    "            #dp[i-1]=[(a-(stations[i][0]-stations[i-1][0])) for a in dp[i-1]]\n",
    "            for j in range(i+1):\n",
    "                if j==0:\n",
    "                    dp[i][j]=dp[i-1][j]\n",
    "                    continue\n",
    "                if dp[i-1][j-1]>=stations[i][0]:\n",
    "                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+stations[i][1])\n",
    "                else:\n",
    "                    dp[i][j]=dp[i-1][j]\n",
    "        #r=[(a-(target-stations[-1][0])) for a in dp[-1]]\n",
    "        for j in range(n):\n",
    "            if dp[-1][j]>=target:\n",
    "                return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        n = len(stations)\n",
    "        \n",
    "        dp = [[0] * (n + 1) for _ in range(n + 1)]   #dp[i][j]表示到第i个加油站加j次油最多能到的距离\n",
    "\n",
    "        if startFuel >= target:\n",
    "            return 0\n",
    "\n",
    "        for i in range(n + 1):\n",
    "            dp[i][0] = startFuel\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, i + 1):\n",
    "                #本站不加油\n",
    "                if dp[i - 1][j] >= stations[i - 1][0]:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "                #本站加油\n",
    "                if dp[i - 1][j - 1] >= stations[i - 1][0]:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + stations[i - 1][1])\n",
    "        for j in range(1, n + 1):\n",
    "            if dp[n][j] >= target:\n",
    "                return j\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        if target<=startFuel:\n",
    "            return 0\n",
    "        n=len(stations)\n",
    "        if n==0:\n",
    "            return -1\n",
    "\n",
    "        # dp[i][j]代表经过前j个站，加了i次油后能到的最远距离\n",
    "        dp=[[-100 for i in range(n+1)] for j in range(n+1)]  \n",
    "        dp[0][0]=startFuel\n",
    "        for j in range(1, n+1):\n",
    "            if stations[j-1][0]<=startFuel:\n",
    "                dp[0][j]=startFuel\n",
    "        print(dp[0])\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            # j=i的情况\n",
    "            if dp[i-1][i-1]<stations[i-1][0]:\n",
    "                return -1\n",
    "            else:\n",
    "                dp[i][i]=dp[i-1][i-1]+stations[i-1][1]\n",
    "                if dp[i][i]>=target:\n",
    "                    return i\n",
    "            for j in range(i+1, n+1):\n",
    "                # 到达不了的情况\n",
    "                if dp[i][j-1]<stations[j-1][0]:\n",
    "                    break\n",
    "                else:\n",
    "                    dp[i][j]=dp[i][j-1]\n",
    "                    if dp[i-1][j-1]>=stations[j-1][0]:\n",
    "                        dp[i][j]=max(dp[i][j], dp[i-1][j-1]+stations[j-1][1])\n",
    "                    if dp[i][j]>=target:\n",
    "                        return i\n",
    "            print(dp[i])\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        n = len(stations)\n",
    "        \n",
    "        dp = [[0] * (n + 1) for _ in range(n + 1)]   #dp[i][j]表示到第i个加油站加j次油最多能到的距离\n",
    "\n",
    "        if startFuel >= target:\n",
    "            return 0\n",
    "\n",
    "        for i in range(n + 1):\n",
    "            dp[i][0] = startFuel\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, i + 1):\n",
    "                #本站不加油\n",
    "                if dp[i - 1][j] >= stations[i - 1][0]:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "                #本站加油\n",
    "                if dp[i - 1][j - 1] >= stations[i - 1][0]:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + stations[i - 1][1])\n",
    "        for j in range(1, n + 1):\n",
    "            if dp[n][j] >= target:\n",
    "                return j\n",
    "        return -1\n",
    "\n",
    "\n",
    "#https://www.bilibili.com/video/BV1Rp4y1U7HE?from=search&seid=11726406931422863134\n",
    "#https://leetcode-cn.com/problems/minimum-number-of-refueling-stops/solution/jian-ji-pythoner-wei-dong-tai-gui-hua-by-jhhuang/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        if startFuel >= target:\n",
    "            return 0\n",
    "        dp = [[startFuel] * len(stations) for _ in range(len(stations) + 1)]\n",
    "        for i in range(1, len(stations) + 1):\n",
    "            if startFuel >= stations[0][0]:\n",
    "                dp[i][0] += stations[0][1]\n",
    "\n",
    "        rst = -1\n",
    "        for i in range(1, len(stations) + 1):\n",
    "            for j in range(i - 1, len(stations)):\n",
    "                if dp[i - 1][j] >= stations[j][0]:\n",
    "                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1] + stations[j][1])\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])\n",
    "                if dp[i][j] >= target:\n",
    "                    rst = i\n",
    "                    break\n",
    "            if rst >= 0:\n",
    "                break\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        n = len(stations)\n",
    "        dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]\n",
    "        if startFuel >= target:\n",
    "            return 0\n",
    "        for i in range(n + 1):\n",
    "            dp[i][0] = startFuel\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, i + 1):\n",
    "                if dp[i - 1][j] >= stations[i - 1][0]:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "                if dp[i - 1][j - 1] >= stations[i - 1][0]:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + stations[i - 1][1])\n",
    "        for i in range(n + 1):\n",
    "            if dp[n][i] >= target:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        n = len(stations)\n",
    "        # dp[i][j]表示经过第i个加油站加油j次能够到达的最远距离\n",
    "        dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]\n",
    "        if startFuel >= target:\n",
    "            return 0\n",
    "        for i in range(n + 1):\n",
    "            dp[i][0] = startFuel\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, i + 1):\n",
    "                # 前i-1站加j次，本站不加油\n",
    "                if dp[i - 1][j] >= stations[i - 1][0]:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "                # 前i-1站加j-1次，本站加油\n",
    "                if dp[i - 1][j - 1] >= stations[i - 1][0]:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + stations[i - 1][1])\n",
    "        for i in range(n + 1):\n",
    "            if dp[n][i] >= target:\n",
    "                return i\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        if not stations:\n",
    "            return 0 if startFuel >= target else -1\n",
    "        dp = [[math.inf]*(len(stations)+1) for _ in range(len(stations))]\n",
    "        for sta_left in range(len(dp)): #剩余站数\n",
    "            sta = len(stations) - 1 - sta_left\n",
    "            for add in range(sta_left+2): #加油次数\n",
    "                if sta_left == 0:\n",
    "                    dp[sta_left][add] = max(0,target-stations[sta][0]-(stations[-1][1] if add==1 else 0)) #最后一站\n",
    "                elif add == 0:\n",
    "                    dp[sta_left][add] = max(0,dp[sta_left-1][0] + stations[sta+1][0]-stations[sta][0])\n",
    "                else:\n",
    "                    dont = dp[sta_left-1][add]+stations[sta+1][0]-stations[sta][0]\n",
    "                    do = dp[sta_left-1][add-1]+stations[sta+1][0]-stations[sta][0]-stations[sta][1]\n",
    "                    dp[sta_left][add] = max(min(dont, do),0)\n",
    "        # print(dp)\n",
    "        for i, num in enumerate(dp[-1]):\n",
    "            if num+stations[0][0] <= startFuel:\n",
    "                return i\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        if not stations:\n",
    "            return 0 if startFuel >= target else -1\n",
    "        dp = [[math.inf]*(len(stations)+1) for _ in range(len(stations))]\n",
    "        for sta_left in range(len(dp)): #剩余站数\n",
    "            sta = len(stations) - 1 - sta_left\n",
    "            for add in range(sta_left+2): #加油次数\n",
    "                if sta_left == 0:\n",
    "                    dp[sta_left][add] = max(0,target-stations[sta][0]-(stations[-1][1] if add==1 else 0)) #最后一站\n",
    "                elif add == 0:\n",
    "                    dp[sta_left][add] = max(0,dp[sta_left-1][0] + stations[sta+1][0]-stations[sta][0])\n",
    "                else:\n",
    "                    dont = dp[sta_left-1][add]+stations[sta+1][0]-stations[sta][0]\n",
    "                    do = dp[sta_left-1][add-1]+stations[sta+1][0]-stations[sta][0]-stations[sta][1]\n",
    "                    dp[sta_left][add] = max(min(dont, do),0)\n",
    "        # print(dp)\n",
    "        for i, num in enumerate(dp[-1]):\n",
    "            if num+stations[0][0] <= startFuel:\n",
    "                return i\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        n = len(stations)\n",
    "        # dp[i][j]表示经过第i个加油站加油j次能够到达的最远距离\n",
    "        dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]\n",
    "        if startFuel >= target:\n",
    "            return 0\n",
    "        for i in range(n + 1):\n",
    "            dp[i][0] = startFuel\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, i + 1):\n",
    "                # 前i-1站加j次，本站不加油\n",
    "                if dp[i - 1][j] >= stations[i - 1][0]:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "                # 前i-1站加j-1次，本站加油\n",
    "                if dp[i - 1][j - 1] >= stations[i - 1][0]:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + stations[i - 1][1])\n",
    "        for i in range(n + 1):\n",
    "            if dp[n][i] >= target:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        nums = len(stations)\n",
    "        if nums == 0 and startFuel >= target:\n",
    "            return 0\n",
    "        dp = [[0 for _ in range(nums+1)] for _ in range(nums+1)]\n",
    "        dp[0] = [startFuel for _ in range(nums+1)]\n",
    "        for i in range(nums+1):\n",
    "            dp[i][0] = startFuel\n",
    "        for i in range(1, nums+1):      # 加油站个数\n",
    "            loc = stations[i-1][0]\n",
    "            fuel = stations[i-1][1]\n",
    "            for j in range(1, i+1):   # 加油次数\n",
    "                if dp[i-1][j] >= loc:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                if dp[i-1][j-1] >= loc:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i-1][j-1]+fuel)\n",
    "        for j in range(nums+1):\n",
    "            for i in range(nums+1):\n",
    "                if dp[i][j] >= target:\n",
    "                    return j\n",
    "\n",
    "        return -1\n",
    "             \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        n = len(stations)\n",
    "        # dp[i][j]表示经过第i个加油站加油j次能够到达的最远距离\n",
    "        dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]\n",
    "        if startFuel >= target:\n",
    "            return 0\n",
    "        for i in range(n + 1):\n",
    "            dp[i][0] = startFuel\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, i + 1):\n",
    "                # 前i-1站加j次，本站不加油\n",
    "                if dp[i - 1][j] >= stations[i - 1][0]:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "                # 前i-1站加j-1次，本站加油\n",
    "                if dp[i - 1][j - 1] >= stations[i - 1][0]:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + stations[i - 1][1])\n",
    "        for i in range(n + 1):\n",
    "            if dp[n][i] >= target:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        n = len(stations)\n",
    "        if startFuel >= target:\n",
    "            return 0 \n",
    "        # dp[i][j]代表从前i个加油站经过（前i个物品可以拿的情况下）\n",
    "        # 加油次数最大为j的情况下（背包最大容量是j）\n",
    "        # 所能开的最远距离（产生的最大价值）\n",
    "        dp = [[0 for _ in range(n+1)] for _ in range(n+1)]\n",
    "        # base case\n",
    "        # dp[0][...] = startFuel? 0 ?\n",
    "        # 不管经过多少加油站就算一次油也不加，最大能达里程也是startFuel\n",
    "        for i in range(n+1):\n",
    "            dp[i][0] = startFuel\n",
    "        min_fuel = -1\n",
    "        # 为什么这边遍历物品的时候也需要从1开始\n",
    "        # 因为连第一个加油站也不能确定能不能到达\n",
    "        # 所以如果不是n+1，第0个物品不好初始化\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, i+1):\n",
    "                # 加油、不加油取最大值\n",
    "                # 此时背包问题中消耗的重量为加油次数就是1\n",
    "                not_fuel = dp[i-1][j]\n",
    "                fuel = dp[i-1][j-1]\n",
    "                # 如果要选择加油\n",
    "                # 那上一次状态dp[i-1][j-1]所能达到的最大里程必须要能达到当前加油站的位置才行\n",
    "                dp[i][j] = dp[i-1][j]\n",
    "                if fuel >= stations[i-1][0]:\n",
    "                    dp[i][j] = max(not_fuel, fuel + stations[i-1][1])\n",
    "                if i == n and dp[i][j] >= target:\n",
    "                    return j\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        n = len(stations)\n",
    "        if startFuel >= target:\n",
    "            return 0 \n",
    "        # dp[i][j]代表从前i个加油站经过（前i个物品可以拿的情况下）\n",
    "        # 加油次数最大为j的情况下（背包最大容量是j）\n",
    "        # 所能开的最远距离（产生的最大价值）\n",
    "        dp = [[0 for _ in range(n+1)] for _ in range(n+1)]\n",
    "        # base case\n",
    "        # dp[0][...] = startFuel? 0 ?\n",
    "        # 不管经过多少加油站就算一次油也不加，最大能达里程也是startFuel\n",
    "        for i in range(n+1):\n",
    "            dp[i][0] = startFuel\n",
    "        min_fuel = -1\n",
    "        # 为什么这边遍历物品的时候也需要从1开始\n",
    "        # 因为连第一个加油站也不能确定能不能到达\n",
    "        # 所以如果不是n+1，第0个物品不好初始化\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, i+1):\n",
    "                # 加油、不加油取最大值\n",
    "                # 此时背包问题中消耗的重量为加油次数就是1\n",
    "                not_fuel = dp[i-1][j]\n",
    "                fuel = dp[i-1][j-1]\n",
    "                # 如果要选择加油\n",
    "                # 那上一次状态dp[i-1][j-1]所能达到的最大里程必须要能达到当前加油站的位置才行\n",
    "                dp[i][j] = dp[i-1][j]\n",
    "                if fuel >= stations[i-1][0]:\n",
    "                    dp[i][j] = max(not_fuel, fuel + stations[i-1][1])\n",
    "                if i == n and dp[i][j] >= target:\n",
    "                    return j\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        # 1. 动态规划 O(n**2)\n",
    "        # dp[i][j] 通过前i个加油站, 加j次油, 最多到达的位置\n",
    "        n = len(stations)\n",
    "        dp = [[0]*(n+1) for _ in range(n+1)]\n",
    "        # 初始化\n",
    "        for i in range(n+1):\n",
    "            dp[i][0] = startFuel\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, i+1):\n",
    "                dp[i][j] = dp[i-1][j]\n",
    "                if dp[i-1][j-1] >= stations[i-1][0]:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i-1][j-1] + stations[i-1][1])\n",
    "        for j in range(n+1):\n",
    "            if dp[n][j] >= target:\n",
    "                return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        if startFuel >= target: return 0\n",
    "        if not stations: return -1\n",
    "        n = len(stations)\n",
    "        # 1. 动态规划\n",
    "        # dp[i][j] 在i个加油站最多加j次油最远到达的距离 j<=i\n",
    "        # dp[i][j] = dp[i-1][j-1]+stations[i][1] if stations[i][1]<=dp[i-1][j-1], dp[i-1][j]\n",
    "        dp = [[0]*(n+1) for j in range(n+1)]\n",
    "        dp[0][0] = startFuel\n",
    "        for i in range(1, n+1):\n",
    "            dp[i][0] = dp[i-1][0] if stations[i-1][0]<=dp[i-1][0] else 0\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, i+1):\n",
    "                dp[i][j] = dp[i-1][j]\n",
    "                if dp[i-1][j-1] >= stations[i-1][0]:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i-1][j-1]+stations[i-1][1])\n",
    "\n",
    "        ans = -1\n",
    "        for j in range(n+1):\n",
    "            if dp[n][j] >= target:\n",
    "                return j\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        #优先队列\n",
    "        '''from queue import PriorityQueue\n",
    "        count,miles,queue=0,startFuel,PriorityQueue()\n",
    "        stations.append([target,-1])\n",
    "        for st in stations:\n",
    "            if miles<st[0]:\n",
    "                while queue.qsize()>0 and miles<st[0]:\n",
    "                    fuel=-queue.get()\n",
    "                    miles+=fuel\n",
    "                    count+=1\n",
    "                if miles<st[0]:return -1\n",
    "            queue.put(-st[1])\n",
    "        return count'''\n",
    "        if startFuel>=target:return 0\n",
    "        n=len(stations)\n",
    "        dp=[[0]*(n+1) for i in range(n+1)] #dp[i][j]表示到达第i个加油站加油j次最长行驶里程\n",
    "        #初始化\n",
    "        for j in range(n):\n",
    "            #dp[0][j]=startFuel\n",
    "            dp[j][0]=startFuel\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,i+1):\n",
    "                #if dp[i-1][j]>=stations[i-1][0]:#第i站不加油\n",
    "                dp[i][j]=dp[i-1][j]\n",
    "                if dp[i-1][j-1]>=stations[i-1][0]:#第i站加油\n",
    "                    dp[i][j]=max(dp[i][j],dp[i-1][j-1]+stations[i-1][1])\n",
    "        for j in range(n+1):\n",
    "            if dp[n][j]>=target:\n",
    "                return j\n",
    "        return -1\n",
    "           \n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        # stations.append([target, 0])\n",
    "        n = len(stations)\n",
    "        dp = [[-float('inf')] * (n + 1) for i in range(n)]\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i + 1):\n",
    "        #         # i: station index, j: stop num\n",
    "        #         if j == 0:\n",
    "        #             if startFuel - stations[i][0] >= 0:\n",
    "        #                 dp[i][j] = startFuel - stations[i][0] + stations[i][1]\n",
    "        #         else:\n",
    "        #             for ii in range(i):\n",
    "        #                 if dp[ii][j - 1] >= stations[i][0] - stations[ii][0]:\n",
    "        #                     left_gas = dp[ii][j - 1] - (stations[i][0] - stations[ii][0]) + stations[i][1]\n",
    "        #                     if left_gas > dp[i][j]:\n",
    "        #                         dp[i][j] = left_gas\n",
    "        #         # print(i, j, dp[i][j])\n",
    "        # for i in range(n):\n",
    "        #     if dp[n - 1][i] >= 0:\n",
    "        #         return i\n",
    "\n",
    "        # return -1\n",
    "        # 0 - i个加油站加油j次\n",
    "        if len(stations) == 0:\n",
    "            if startFuel >= target:\n",
    "                return 0\n",
    "            else:\n",
    "                return -1\n",
    "        min_time = 600\n",
    "        for i in range(n):\n",
    "            for j in range(i + 2):\n",
    "                if i == 0 and j == 0:\n",
    "                    dp[i][j] = startFuel\n",
    "                elif i == 0 and j == 1:\n",
    "                    if startFuel >= stations[0][0]:\n",
    "                        dp[i][j] = startFuel + stations[0][1]\n",
    "\n",
    "                else:\n",
    "                    if dp[i - 1][j - 1] >= stations[i][0]:\n",
    "                        dp[i][j] = max(dp[i - 1][j - 1] + stations[i][1], dp[i][j])\n",
    "                    dp[i][j] = max(dp[i - 1][j], dp[i][j])\n",
    "                # print(i, j, dp[i][j])\n",
    "                if dp[i][j] >= target:\n",
    "                    min_time = min(min_time, j)\n",
    "        if min_time == 600:\n",
    "            return -1\n",
    "        else:\n",
    "            return min_time\n",
    "\n",
    "\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        if startFuel >= target:\n",
    "            return 0\n",
    "        if sum([val for point, val in stations]) + startFuel < target:\n",
    "            return -1\n",
    "        n = len(stations)\n",
    "        ans = n\n",
    "        # n+1是因为可以加一个在位置0，加0次油的情况，对应的dp值是startFuel\n",
    "        # 这样一来，加油站的起始下标需要改为1\n",
    "        dp = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        for i in range(n):\n",
    "            dp[i][0] = startFuel\n",
    "        # 对加油站下标遍历\n",
    "        for i in range(n):\n",
    "            # 所有dp的下标都应+1看待，这里表示，如果在前i个加油站每个都加油，\n",
    "            # 都无法到达第i+1个加油站，也就是下标为i的加油站，则说明后面的位置都不可达了。\n",
    "            if dp[i][i] < stations[i][0]:\n",
    "                return -1\n",
    "            # 对加油次数做遍历，截至下标i的加油站，也就是第i+1个加油站，最多可以加i+1次油\n",
    "            # 反向遍历是因为如果遍历到某个加油次数，已无法到目前考虑的这个加油站，则更少的加油次数也无法到达\n",
    "            for j in range(i, 0, -1):\n",
    "                # 如果在前i个加油站加j-1次油就可以到位置stations[i]，也就是第i+1个加油站，\n",
    "                # 则截至第i+1个加油站，总共加j次油可以到达的最远距离可以是前面加j-1次，\n",
    "                # 然后再加上当前这个加油站的油量，或者前面就已经加j次\n",
    "                if dp[i][j - 1] >= stations[i][0]:\n",
    "                    dp[i + 1][j] = max(dp[i][j - 1] + stations[i][1], dp[i][j])\n",
    "                    if dp[i + 1][j] >= target:\n",
    "                        ans = min(ans, j)\n",
    "                else:\n",
    "                    dp[i + 1][j] = dp[i][j]\n",
    "            # 截至第i+1个加油站要加i+1次油必然是每个加油站都加油\n",
    "            dp[i + 1][i + 1] = dp[i][i] + stations[i][1]\n",
    "            if dp[i + 1][i + 1] >= target:\n",
    "                ans = min(ans, i + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        l = len(stations)\n",
    "        if 0 == l:\n",
    "            return -1 if target > startFuel else 0\n",
    "        dp = [None for _ in range(l)]\n",
    "        s = stations[0]\n",
    "        if startFuel >= target:\n",
    "            return 0\n",
    "        elif s[0] > startFuel:\n",
    "            return -1\n",
    "        elif s[1] + startFuel >= target:\n",
    "            return 1\n",
    "        # (dist, fuel, times)\n",
    "        if startFuel - s[0] > 0:\n",
    "            dp[0] = [[target - s[0], startFuel - s[0] + s[1], 1], [target - s[0], startFuel - s[0], 0]]\n",
    "        else:\n",
    "            dp[0] = [[target - s[0], startFuel - s[0] + s[1], 1]]\n",
    "        # print(dp)\n",
    "        ret = -1\n",
    "        for i in range(1, l):\n",
    "            s = stations[i]\n",
    "            if dp[i - 1]:\n",
    "                d = s[0] - stations[i - 1][0]\n",
    "                m = {}\n",
    "                for c in dp[i - 1]:\n",
    "                    r = c[0] - d\n",
    "                    if c[1] - d >=0:\n",
    "                        f = c[1] - d + s[1]\n",
    "                        if f >= r:\n",
    "                            # print(\"can finish\")\n",
    "                            if c[2] + 1 < ret or -1 == ret:\n",
    "                                ret = c[2] + 1\n",
    "                        else:\n",
    "                            k1, k2 = c[2] + 1, c[2]\n",
    "                            v1, v2 = [r, f, k1], [r, c[1] - d, k2]\n",
    "                            if None == dp[i]:\n",
    "                                dp[i] = [v1, v2]\n",
    "                                m[k1] = v1\n",
    "                                m[k2] = v2\n",
    "                            else:\n",
    "                                if k1 in m:\n",
    "                                    pf = m[k1][1]\n",
    "                                    m[k1][1] = max(pf, v1[1])\n",
    "                                else:\n",
    "                                    dp[i].append(v1)\n",
    "                                    m[k1] = v1\n",
    "\n",
    "                                if k2 in m:\n",
    "                                    pf = m[k2][1]\n",
    "                                    m[k2][1] = max(pf, v2[1])\n",
    "                                else:\n",
    "                                    dp[i].append(v2)\n",
    "                                    m[k2] = v2\n",
    "                            # print(f\"i {i} dpn {len(dp[i])}\")\n",
    "                # print(dp)\n",
    "            else:\n",
    "                # print(f\"term\")\n",
    "                break\n",
    "        # print(dp)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        if not stations:\n",
    "            if target > startFuel:\n",
    "                return -1\n",
    "            return 0\n",
    "        dp = [[-1]*len(stations) for _ in range(len(stations))]\n",
    "        for i in range(len(stations)):\n",
    "            if i == 0:\n",
    "                dp[i][0] = startFuel - stations[i][0]\n",
    "            else:\n",
    "                last_fuel = stations[i-1][1]\n",
    "                this_dist = stations[i][0] - stations[i-1][0]\n",
    "                for j in range(i+1):\n",
    "                    l_j = []\n",
    "                    if dp[i-1][j] >= 0:\n",
    "                        l_j.append(dp[i-1][j]-this_dist)\n",
    "                    if j>0 and dp[i-1][j-1]>=0:\n",
    "                        l_j.append(dp[i-1][j-1]+last_fuel-this_dist)\n",
    "                    if l_j:\n",
    "                        dp[i][j] = max(l_j)\n",
    "            if dp[i][i]<0:\n",
    "                return -1\n",
    "        last_fuel = stations[-1][1]\n",
    "        this_dist = target - stations[-1][0]\n",
    "        for i in range(len(stations)):\n",
    "            if dp[-1][i] < 0:\n",
    "                continue\n",
    "            if dp[-1][i] - this_dist >= 0:\n",
    "                return i\n",
    "            if dp[-1][i] + last_fuel - this_dist >= 0:\n",
    "                return i+1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        stations.append([target, 0])\n",
    "        n = len(stations)\n",
    "        # ans[i][j] = k 代表到第i 个加油站(刚到，未加油时)，一共加油j 次，最多还剩k 升油\n",
    "        ans = [[-1]*n for _ in range(n)]\n",
    "        tttmp = startFuel - stations[0][0]\n",
    "        ans[0][0] = tttmp if tttmp >= 0 else -float('inf')\n",
    "        for i in range(1, n):\n",
    "            cost = stations[i][0] - stations[i-1][0]\n",
    "            ttmp = startFuel - stations[i][0]\n",
    "            ans[i][0] = ttmp if ttmp >= 0 else -float('inf')\n",
    "            for j in range(1, i+1):\n",
    "                tmp = max(ans[i-1][j] , ans[i-1][j-1] + stations[i-1][1]) - cost\n",
    "                ans[i][j] = tmp if tmp >= 0 else -float('inf')\n",
    "\n",
    "        for i in range(n):\n",
    "            if ans[-1][i] >= 0:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        n = len(stations)\n",
    "        \n",
    "        if startFuel >= target:\n",
    "            return 0\n",
    "        \n",
    "        if n == 0:\n",
    "            return -1\n",
    "\n",
    "        dp = [[-1] * (n + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = startFuel\n",
    "        min_stop = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            distance = stations[i][0] - (stations[i - 1][0] if i else 0)\n",
    "            if dp[i][i] < distance:\n",
    "                return -1\n",
    "            for stop in range(i, min_stop - 1, -1):\n",
    "                if dp[i][stop] >= distance:\n",
    "                    dp[i][stop] -= distance\n",
    "                    dp[i + 1][stop] = dp[i][stop]\n",
    "                else:\n",
    "                    min_stop = stop + 1\n",
    "                    break\n",
    "            #print('1:', dp, f\"min={min_stop}, i={i}, dis={distance}\")\n",
    "            for stop in range(min_stop, i + 1):\n",
    "                dp[i + 1][stop + 1] = max(dp[i + 1][stop + 1], dp[i][stop] + stations[i][1])\n",
    "            #print('2:', dp)\n",
    "        \n",
    "        diff = target - stations[-1][0]\n",
    "        #print(diff)\n",
    "        for stop in range(min_stop, n + 1):\n",
    "            if dp[-1][stop] >= diff:\n",
    "                return stop\n",
    "        return -1 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self,target:int,startFuel:int,stations:List[List[int]])->int:\n",
    "        n=len(stations)\n",
    "        dp=[[0 for _ in range(0,n+1)] for _ in range(0,n+1)]\n",
    "        dp[0][0]=startFuel\n",
    "        for i in range(1,n+1):\n",
    "            dp[i][0]=startFuel\n",
    "            for j in range(1,i+1):\n",
    "                if dp[i-1][j-1]<stations[i-1][0]:\n",
    "                    dp[i][j]=dp[i-1][j]       #不加油\n",
    "                else:\n",
    "                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+stations[i-1][1])\n",
    "        for j in range(0,n+1):\n",
    "            if dp[n][j]>=target:return j\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        if startFuel>=target:\n",
    "            return 0\n",
    "        lent = len(stations)\n",
    "        dp = [[0]*(lent+1) for _ in range(lent+1)]\n",
    "        for i in range(lent+1):\n",
    "            dp[i][0] = startFuel \n",
    "        for i in range(1,lent+1):\n",
    "            for j in range(1,lent+1):\n",
    "                # 不加油能走多远\n",
    "                if dp[i-1][j]>=stations[i-1][0]:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                # 加油能走多远\n",
    "                if dp[i-1][j-1]>=stations[i-1][0]:\n",
    "                    dp[i][j] = max(dp[i][j],dp[i-1][j-1]+stations[i-1][1]) # 取两者最大值\n",
    "        for j in range(lent+1):\n",
    "            if dp[lent][j]>=target:\n",
    "                return j\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        # n = len(stations)\n",
    "        # # dp[i]：加i次油能走的最远距离\n",
    "        # dp = [startFuel] + [0] * n\n",
    "        # for i, (location, capacity) in enumerate(stations):\n",
    "        #     for j in range(i, -1, -1):\n",
    "        #         if dp[j] >= location:\n",
    "        #             dp[j+1] = max(dp[j+1], dp[j] + capacity)\n",
    "\n",
    "        # for i in range(n+1):\n",
    "        #     if dp[i] >= target: return i\n",
    "        # return -1\n",
    "\n",
    "        n = len(stations)\n",
    "        # dp[i][j]表示经过第i个加油站加油j次能够到达的最远距离\n",
    "        dp = [[startFuel] + [0]*n for _ in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, i + 1):\n",
    "                # 前i-1站加j次，本站不加油\n",
    "                if dp[i - 1][j] >= stations[i - 1][0]:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "                # 前i-1站加j-1次，本站加油\n",
    "                if dp[i - 1][j - 1] >= stations[i - 1][0]:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + stations[i - 1][1])\n",
    "        for i in range(n + 1):\n",
    "            if dp[n][i] >= target:\n",
    "                return i\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        sta_n=len(stations)\n",
    "        if startFuel>=target:return 0\n",
    "        dp=[[0 for j in range(sta_n+1)] for i in range(sta_n+1)]\n",
    "        ans=sta_n+1\n",
    "        for i in range(sta_n+1):\n",
    "            for j in range(i+1):\n",
    "                if j==0:\n",
    "                    dp[i][j]=startFuel\n",
    "                elif i==0:\n",
    "                    dp[i][j]=startFuel\n",
    "                else:\n",
    "                    if dp[i-1][j]>=stations[i-1][0]:\n",
    "                        dp[i][j]=max(dp[i-1][j],dp[i][j])\n",
    "                    if dp[i-1][j-1]>=stations[i-1][0]:\n",
    "                        dp[i][j]=max(dp[i-1][j-1]+stations[i-1][1],dp[i][j])\n",
    "                if dp[i][j]>=target:\n",
    "                    ans=min(ans,j)\n",
    "        # for i in dp:\n",
    "        #     print(i)\n",
    "        if ans==sta_n+1:\n",
    "            return -1\n",
    "        else:\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        # import numpy as np\n",
    "        n = len(stations)\n",
    "        # dp = -np.ones((n+5, n+5), dtype=int)\n",
    "        dp = [[-1]*(n+5)]\n",
    "        dp[0][0] = 0\n",
    "        dp[0][1] = startFuel\n",
    "        stations = [[0,startFuel]]+stations\n",
    "        stations.append([target, 0])\n",
    "        n += 2\n",
    "        for i in range(1,n):\n",
    "            dp.append([-1]*(n+5))\n",
    "            for j in range(1, i+2):\n",
    "                dist = stations[i][0]-stations[i-1][0]\n",
    "                dp[i][j] = -1\n",
    "                if dp[i-1][j-1] >= dist:\n",
    "                    dp[i][j] = dp[i-1][j-1]-dist + stations[i][1]\n",
    "                if dp[i-1][j] >= dist:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i-1][j]-dist)\n",
    "        # print(dp)\n",
    "        for i in range(1, n+2):\n",
    "            if dp[n-1][i] != -1:\n",
    "                return i-1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        fuel = startFuel\n",
    "        cur = 0\n",
    "        for dis, f in stations:\n",
    "            if dis - cur > fuel:\n",
    "                return -1\n",
    "            fuel -= dis - cur - f\n",
    "            cur = dis\n",
    "        if fuel < target - cur:\n",
    "            return -1\n",
    "        \n",
    "        stations.append([target, 0])\n",
    "        \n",
    "        l, r = -1, len(stations) - 1\n",
    "        while l < r - 1:\n",
    "            mid = (l + r) // 2\n",
    "            dp = [[-1] * (mid + 1) for _ in range(len(stations) + 1)]\n",
    "            for i in range(len(stations) + 1):\n",
    "                for j in range(mid + 1):\n",
    "                    if i == 0 and j == 0:\n",
    "                        dp[i][j] = startFuel\n",
    "                    elif i == 0:\n",
    "                        continue\n",
    "                    elif j == 0:\n",
    "                        if i == 1:\n",
    "                            dp[i][j] = max(-1, dp[i - 1][j] - stations[i - 1][0])\n",
    "                        else:\n",
    "                            dp[i][j] = max(-1, dp[i - 1][j] - stations[i - 1][0] + stations[i - 2][0])\n",
    "                    else:\n",
    "                        if i == 1:\n",
    "                            continue\n",
    "                        dp[i][j] = max(-1, dp[i - 1][j] - stations[i - 1][0] + stations[i - 2][0])\n",
    "                        if dp[i - 1][j - 1] > -1:\n",
    "                            dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + stations[i - 2][1] - stations[i - 1][0] + stations[i - 2][0])\n",
    "            # for row in dp:\n",
    "            #     print(row)\n",
    "            if dp[-1][-1] >= 0:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        stations.append([target, 0])\n",
    "        n = len(stations)\n",
    "        dp = [[0] * n for _ in range(n)]  # 经过第i个加油站的时候，加了j次油最多可以跑多远\n",
    "        dp[0][0] = startFuel\n",
    "        diff_arr = []\n",
    "        last = 0\n",
    "        for i, s in enumerate(stations):\n",
    "            diff_arr.append(s[0] - last)\n",
    "            last = s[0]\n",
    "        for i in range(1,n):\n",
    "            for j in range(i+1):\n",
    "                if j != 0 and dp[i-1][j-1] >= diff_arr[i-1]:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + stations[i-1][1]) - diff_arr[i-1]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j] - diff_arr[i-1]\n",
    "                if dp[i][j] < 0:\n",
    "                    dp[i][j] = -math.inf\n",
    "\n",
    "        if dp[n-1][n-1] < diff_arr[-1]:\n",
    "            return -1\n",
    "        for j in range(n):\n",
    "            if dp[n-1][j] >= diff_arr[-1]:\n",
    "                return j\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        \"\"\"动态规划 dp[i][j]:到达第i+1个加油站，停靠j次所有的最多油量\"\"\"\n",
    "        if not stations:\n",
    "            if startFuel >= target:\n",
    "                return 0\n",
    "            else:\n",
    "                return -1\n",
    "        dp = [[0 for _ in range(len(stations)+1)]for _ in range(len(stations)+1)]\n",
    "        dp[0][0] = startFuel\n",
    "        for i in range(1,len(stations)+1):\n",
    "            distance = stations[i-1][0] - stations[i-2][0] if i > 1 else stations[i-1][0] \n",
    "            for j in range(len(stations)+1):\n",
    "                if (dp[i][j] < 0) or (j>i):\n",
    "                    break\n",
    "                if j == 0:\n",
    "                    dp[i][j] = dp[i-1][j] - distance\n",
    "                else:\n",
    "                    dp[i][j] = max((dp[i-1][j] - distance),dp[i-1][j-1] - distance+stations[i-1][1])  if dp[i-1][j-1] >= distance else (dp[i-1][j] - distance)\n",
    "        for i in range(len(stations)+1):\n",
    "            if dp[len(stations)][i] >= (target - stations[-1][0]):\n",
    "                return i\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        \"\"\"动态规划 dp[i][j]:到达第i+1个加油站，停靠j次所有的最多油量\"\"\"\n",
    "        if not stations:\n",
    "            if startFuel >= target:\n",
    "                return 0\n",
    "            else:\n",
    "                return -1\n",
    "        dp = [[0 for _ in range(len(stations)+1)]for _ in range(len(stations)+1)]\n",
    "        dp[0][0] = startFuel\n",
    "        for i in range(1,len(stations)+1):\n",
    "            distance = stations[i-1][0] - stations[i-2][0] if i > 1 else stations[i-1][0] \n",
    "            for j in range(len(stations)+1):\n",
    "                if (dp[i][j] < 0) or (j>i):\n",
    "                    break\n",
    "                if j == 0:\n",
    "                    dp[i][j] = dp[i-1][j] - distance\n",
    "                else:\n",
    "                    dp[i][j] = max((dp[i-1][j] - distance),dp[i-1][j-1] - distance+stations[i-1][1])  if dp[i-1][j-1] >= distance else (dp[i-1][j] - distance)\n",
    "        for i in range(len(stations)+1):\n",
    "            if dp[len(stations)][i] >= (target - stations[-1][0]):\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        # dp\n",
    "        # f[i][j] = 到第i个加油站，并且加了j次油的剩余油量\n",
    "        # f[i][j] = f[i - 1][j] - (dis[i] - dis[i - 1])\n",
    "        # f[i][j] = f[i - 1][j - 1] + fuel[i - 1] - (dis[i] - dis[i - 1])\n",
    "        stations.append([target,0])\n",
    "        n = len(stations)\n",
    "        f = [[-1] * (n + 1) for _ in range(n + 1)]\n",
    "        f[0][0] = startFuel\n",
    "        for i in range(1,n + 1) :\n",
    "            dis,fuel = stations[i - 1]\n",
    "            predis = 0 if i == 1 else stations[i - 2][0]\n",
    "            prefuel = 0 if i == 1 else stations[i - 2][1]\n",
    "            for j in range(i + 1) :\n",
    "                no_refueling = refueling = -1\n",
    "                if f[i - 1][j] >= 0 :\n",
    "                    no_refueling = f[i - 1][j] - (dis - predis)\n",
    "                    # print(i,j,no_refueling)\n",
    "                if f[i - 1][j - 1] >= 0 :\n",
    "                    refueling = f[i - 1][j - 1] - (dis - predis) + prefuel\n",
    "                    # print(i,j,refueling)\n",
    "                f[i][j] = max(no_refueling,refueling)\n",
    "\n",
    "        # print(f)\n",
    "        # print(stations)\n",
    "        for i in range(n) :\n",
    "            if f[n][i] >= 0 :\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, s: List[List[int]]) -> int:\n",
    "        n = len(s)\n",
    "        s = [[0, startFuel]] + s + [[target, 0]]\n",
    "        print(s)\n",
    "        f = [[-1]* (i+2) for i in range(n+2)]\n",
    "        f[0][0] = startFuel\n",
    "\n",
    "        for i in range(1, n+2):\n",
    "            for j in range(0, i+1):\n",
    "                dist = s[i][0] - s[i-1][0]\n",
    "                f[i][j] = max(f[i][j], f[i-1][j]-dist)\n",
    "                if j and f[i-1][j-1]>=dist:\n",
    "                    f[i][j] = max(f[i][j], f[i-1][j-1]-dist+s[i][1])\n",
    "        \n",
    "        res = 0\n",
    "        for j in range(0, n+1):\n",
    "            if f[n+1][j]>=0:\n",
    "                return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "\n",
    "        # ret = -1 \n",
    "        # return -1 \n",
    "        if startFuel >= target:\n",
    "            return 0 \n",
    "\n",
    "        stations = [[0, 0] ]+ stations # add a initial station as the start \n",
    "\n",
    "        # print(stations)\n",
    "        n = len(stations)\n",
    "        # print(n)\n",
    "        # 考虑到最后一个车站  油尽可能多  不同加油次数\n",
    "        dp = [ [ -1e9 for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        for j in range(n):\n",
    "        # dp[i][j] 加油次数为 i 次  到 j 个站点所剩 最多油的数目\n",
    "            if startFuel - stations[j][0] >= 0 :\n",
    "                dp[0][j] = startFuel - stations[j][0]\n",
    "\n",
    "        # dp[i][j]  =  max(dp[i-1][k] +  stations[k][1] + stations[j] - stations[k])  for k < j \n",
    "        for i in range( n ): # 最多加\n",
    "            for j in range(1, n):\n",
    "                # for k in range(j):\n",
    "                k = j -1 \n",
    "                    # if k 能开到 j\n",
    "                miles_togo =  stations[j][0] - stations[k][0]\n",
    "                if  dp[i][k] >= miles_togo: # 可以不加油 从 k 开到 j \n",
    "                    dp[i][j] = max(dp[i][j], dp[i][k] - miles_togo)\n",
    "                    \n",
    "                    # 或者加一次油 \n",
    "                if i !=0 and dp[i-1][k] + stations[k][1] >= miles_togo:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i-1][k] - miles_togo + stations[k][1])\n",
    "                    # print(i, j , dp[i][j])\n",
    "\n",
    "\n",
    "        # print(dp)\n",
    "        ret = 501 \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                # print(i, j, dp[i][j], stations[j][1], target - stations[j][0])\n",
    "\n",
    "                if dp[i][j] >= target - stations[j][0]:\n",
    "                    ret = min(ret,  i) \n",
    "                    # print(\"i\", i,j,ret)\n",
    "                if  dp[i][j] + stations[j][1]>= target - stations[j][0]:\n",
    "\n",
    "                    ret = min(i + 1, ret )\n",
    "\n",
    "\n",
    "        return ret if ret != 501 else -1 \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # stations[-1] = \n",
    "\n",
    "        # @lru_cache(maxsize=512)\n",
    "        # def dfs(cur_fuel, idx,  cnt): \n",
    "        #     if idx == n:\n",
    "        #         if idx != 0 and cur_fuel >= target - stations[idx-1][0]  : # can to the target\n",
    "        #             return cnt \n",
    "        #         else:\n",
    "        #             return 501 # cannot to the end \n",
    "        #     elif (idx != 0 and cur_fuel >= target - stations[idx-1][0]  ) :\n",
    "        #         return cnt \n",
    "        #     else:\n",
    "        #         # possible choose or not \n",
    "        #         miles_togo = stations[idx][0] - stations[idx-1][0] if idx != 0 else stations[idx][0]\n",
    "        #         if cur_fuel >= miles_togo:\n",
    "        #             r1 = dfs(cur_fuel - miles_togo, idx + 1, cnt)\n",
    "        #             r2 = dfs(stations[idx][1] + cur_fuel - miles_togo, idx + 1, cnt + 1 )\n",
    "        #             return min(r1, r2)\n",
    "        #         else:\n",
    "        #             return 501 \n",
    "        \n",
    "        # ret = dfs(startFuel, 0, 0)\n",
    "        # return ret if ret != 501 else -1 \n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        if len(stations) == 0: return 0 if startFuel >= target else -1\n",
    "        stations.append([target, 0])\n",
    "        n = len(stations)\n",
    "        dp = [[-1 for _ in range(n + 1)] for _ in range(n + 1)]\n",
    "        dp[0][0] = startFuel\n",
    "        prev = 0\n",
    "        for i, (p, f) in enumerate(stations):\n",
    "            for j in range(n + 1):\n",
    "                if dp[i][j] < (p - prev): continue\n",
    "                dp[i+1][j] = max(dp[i][j]-(p-prev), dp[i+1][j])\n",
    "                dp[i+1][j+1] = max(dp[i][j]+f-(p-prev), dp[i+1][j+1])\n",
    "            prev = p\n",
    "        for i, v in enumerate(dp[-1]):\n",
    "            if v != -1: return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        if len(stations) == 0:\n",
    "            return 0 if startFuel >= target else -1\n",
    "        n = len(stations)\n",
    "        inf = -10000000000\n",
    "        stations = [[0,0]] + stations\n",
    "        dp = [[inf]*(n+1) for _ in range(n+1)]\n",
    "        dp[0][0] = startFuel\n",
    "        for i in range(1, n+1):\n",
    "            if startFuel - stations[i][0] >= 0:\n",
    "                dp[i][0] = startFuel - stations[i][0] \n",
    "            for times in range(1, i+1):\n",
    "                #print(dp[i][times])\n",
    "                if dp[i-1][times] >= stations[i][0] - stations[i-1][0]:\n",
    "                    dp[i][times] = dp[i-1][times] - stations[i][0] + stations[i-1][0]\n",
    "                if dp[i-1][times-1] >= stations[i][0] - stations[i-1][0]:\n",
    "                    dp[i][times] = max(dp[i][times],dp[i-1][times-1] + stations[i][1] - stations[i][0] + stations[i-1][0])\n",
    "        need = target - stations[-1][0]\n",
    "        #print(dp)\n",
    "        for i in range(0, n+1):\n",
    "            if dp[n][i] >= need:\n",
    "                return i \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        stations = [[0,startFuel]] + stations + [[target, 0]]\n",
    "        n = len(stations)\n",
    "        dp = [[-1] * n for _ in range(n)]\n",
    "        dp[0][0] = startFuel\n",
    "        for i in range(1, n):\n",
    "            for j in range(i + 1):\n",
    "                if j == 0:\n",
    "                    if dp[i - 1][0] - stations[i][0] + stations[i - 1][0] >= 0:\n",
    "                        dp[i][j] = dp[i - 1][0] - stations[i][0] + stations[i - 1][0] \n",
    "                elif j == i:\n",
    "                    if dp[i - 1][j - 1] - stations[i][0] + stations[i - 1][0] >= 0:\n",
    "                        dp[i][j] = dp[i - 1][j - 1] - stations[i][0] + stations[i - 1][0] + stations[i][1]\n",
    "                else:\n",
    "                    if dp[i - 1][j - 1] - stations[i][0] + stations[i - 1][0] >= 0:\n",
    "                        dp[i][j] = max(\n",
    "                            dp[i - 1][j - 1] - stations[i][0] + stations[i - 1][0] + stations[i][1],\n",
    "                            dp[i - 1][j] - stations[i][0] + stations[i - 1][0]\n",
    "                        )\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i - 1][j] - stations[i][0] + stations[i - 1][0]\n",
    "        res = - 1\n",
    "        for i in range(n):\n",
    "            if dp[-1][i] >= 0:\n",
    "                return i \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, nums: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        # 在前后补充上起始站 和 结束站 方便进行计算。\n",
    "        nums = [[0, startFuel]] + nums + [[target, 0]]\n",
    "        # print(nums)\n",
    "        f = [[-1] * (n + 2) for _ in range(n + 2)]\n",
    "        f[0][0] = startFuel\n",
    "        for i in range(1, n + 2):\n",
    "            for j in range(i + 1):\n",
    "                # print(f[i - 1][j])\n",
    "                # print(nums[i - 1][0])\n",
    "                # print(nums[i][0])\n",
    "                f[i][j] = max(f[i][j], f[i - 1][j] - (nums[i][0] - nums[i - 1][0]))\n",
    "                if j > 0 and f[i - 1][j - 1] >= nums[i][0] - nums[i - 1][0]:\n",
    "                    f[i][j] = max(f[i][j], f[i - 1][j - 1] - (nums[i][0] - nums[i - 1][0]) + nums[i][1])\n",
    "        # print(f)\n",
    "        for i in range(n + 1):\n",
    "            if f[n + 1][i] >= 0:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        n = len(stations)\n",
    "        dp = [[float(\"-inf\")]*(n + 1) for _ in range(n + 1)]\n",
    "        if not n:\n",
    "            return 0 if startFuel >= target else -1\n",
    "        dp[0][0] = startFuel - stations[0][0]\n",
    "        dp[0][1] = startFuel - stations[0][0] + stations[0][1]\n",
    "        if dp[0][0] < 0:\n",
    "            return -1\n",
    "        for i in range(1, n):\n",
    "            for j in range(i + 1):\n",
    "                v = dp[i - 1][j] - stations[i][0] + stations[i - 1][0]\n",
    "                if v < 0:\n",
    "                    continue\n",
    "                dp[i][j] = max(dp[i][j], v)\n",
    "                dp[i][j + 1] = max(dp[i][j + 1], v + stations[i][1])\n",
    "        qaq = dp[-2]\n",
    "        last = target - stations[-1][0]\n",
    "        qwq = [num for num, i in enumerate(qaq) if i - last >= 0]\n",
    "        return min(qwq) if qwq else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        if not stations:\n",
    "            if startFuel >= target:\n",
    "                return 0\n",
    "            else:\n",
    "                return -1\n",
    "\n",
    "        n = len(stations)\n",
    "        dp = [[-1] * (n+1) for _ in range(n)]\n",
    "        if startFuel < stations[0][0]:\n",
    "            return -1\n",
    "        dp[0][0] = startFuel - stations[0][0]\n",
    "        dp[0][1] = dp[0][0] + stations[0][1]\n",
    "        for i, (pos, vol) in enumerate(stations):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            for k in range(i + 1):\n",
    "                if dp[i - 1][k] >= pos - stations[i - 1][0]:\n",
    "                    dp[i][k] = dp[i - 1][k] - (pos - stations[i - 1][0])\n",
    "            for k in range(i + 1, 0, -1):\n",
    "                if dp[i][k-1] != -1:\n",
    "                    dp[i][k] = max(dp[i][k-1] + vol, dp[i][k])\n",
    "        for k in range(0, n+1):\n",
    "            if dp[n-1][k] >= target - stations[n-1][0]:\n",
    "                return k\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, s: List[List[int]]) -> int:\n",
    "        n = len(s)\n",
    "        s = [[0, startFuel]] + s + [[target, 0]]\n",
    "        print(s)\n",
    "        f = [[-1]*(n+2) for _ in range(n+2)]\n",
    "        f[0][0] = startFuel\n",
    "\n",
    "        for i in range(1, n+2):\n",
    "            for j in range(0, i+1):\n",
    "                dist = s[i][0] - s[i-1][0]\n",
    "                \n",
    "                if f[i-1][j]>=dist:\n",
    "                    f[i][j] = max(f[i][j], f[i-1][j]-dist)\n",
    "                if j and f[i-1][j-1]>=dist:\n",
    "                    f[i][j] = max(f[i][j], f[i-1][j-1]-dist+s[i][1])\n",
    "        \n",
    "        res = 0\n",
    "        for j in range(0, n+1):\n",
    "            if f[n+1][j]>=0:\n",
    "                return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        d = defaultdict(lambda: -1)  # d[(i,j)]表示到达第i个站，已经加油j次\n",
    "        stations = [p for p in stations if p[0] < target]\n",
    "        stations = [[0, 0]] + stations + [[target, 0]]\n",
    "        n = len(stations)\n",
    "\n",
    "        q = deque([(0, 0, startFuel)])\n",
    "        while q:\n",
    "            idx, times, left = q.popleft()\n",
    "            if idx == n - 1:\n",
    "                return times\n",
    "            if d[(idx, times)] > left:\n",
    "                continue\n",
    "            nxt = idx + 1\n",
    "            while nxt < n and left >= 0:\n",
    "                left -= (stations[nxt][0] - stations[nxt - 1][0])  # 消耗\n",
    "                if left >= 0:  # 说明能到达\n",
    "                    new_l = left + stations[nxt][1]\n",
    "                    if new_l > d[(nxt, times + 1)]:\n",
    "                        q.append((nxt, times + 1, new_l))  # 加油\n",
    "                        d[(nxt, times + 1)] = new_l\n",
    "                else:\n",
    "                    break\n",
    "                nxt += 1\n",
    "            if nxt == n:\n",
    "                return times\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:\n",
    "        if startFuel >= target:\n",
    "            return 0\n",
    "\n",
    "        ll = len(stations)\n",
    "        dp = [[-1 for x in range(ll)] for y in range(ll)]\n",
    "        dpmax = [-1 for x in range(ll)]\n",
    "        for i in range(ll):\n",
    "            station = stations[i]\n",
    "            for j in range(i, -1, -1):\n",
    "                if j == 0:\n",
    "                    if station[0] <= startFuel:\n",
    "                        dp[i][j] = station[1] + startFuel\n",
    "                else:\n",
    "                    remax = dpmax[j - 1]\n",
    "                    if station[0] <= remax:\n",
    "                        dp[i][j] = station[1] + remax\n",
    "\n",
    "                if dpmax[j] <= dp[i][j]:\n",
    "                    dpmax[j] = dp[i][j]\n",
    "            # print(dp[i])\n",
    "\n",
    "        # print(dpmax)\n",
    "        for i, x in enumerate(dpmax):\n",
    "            if x >= target:\n",
    "                return i + 1\n",
    "\n",
    "        return -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
